\section{Appendix~\ref{app:moves}: Dealing with Well-Separated Instances}
\label{app:moves}

\subsection{The Proof of Proposition~\ref{prop:middle}}
\label{app:s:middle}

Let us assume that $x_{i_2} < F_1(\vec{x})$ (the other case is symmetric). Then, the agents at $x_{i_1}$ have an incentive to report $x_{i_2}$ and decrease their cost, since $x_{i_2} \in F(\vec{x}_{-i_1}, x_{i_2})$, due to the bounded approximation ratio of $F$. This contradicts $F$'s strategyproofness. \qed


\subsection{The Proof of Proposition~\ref{prop:interval}}
\label{app:s:interval}

Since $F$ has a bounded approximation ratio, the two nearby agents $i_K$ and $i_{K+1}$ are both served by the facility at $F_K(\vec{x})$. By Proposition~\ref{prop:middle}, $F_K(\vec{x}) \geq x_{i_K}$. Moreover, $F_K(\vec{x}) \leq x_{i_{K+1}}$. Otherwise, the agent $i_K$ could report $x_{i_{K+1}}$ and decrease her cost, since $x_{i_{K+1}} \in F(\vec{x}_{-i_K}, x_{i_{K+1}})$, due to the bounded approximation ratio of $F$. \qed


\subsection{Pushing the Pair of the Rightmost Agents to the Right: The Proof of Proposition~\ref{prop:right_cover}}
\label{app:s:push_right}

For simplicity and clarity, we explicitly prove Proposition~\ref{prop:right_cover} only for $2$-Facility Location and well-separated instances with $3$ agents (see Proposition~\ref{prop:right_cover_3agents}). It is not difficult to verify that all the technical arguments only depend on the fact that the two nearby agents stay well-separated from and on the right of the third agent. Therefore, the following propositions generalize to the $K$-Facility Location game and well-separated instances with $K+1$ agents.

In the following, we let $F$ be a nice mechanism for the $2$-Facility Location game with an approximation ratio of at most $\rho$ for instances with $3$ agents.
%
As in Section~\ref{s:3agents}, we use the indices $i, j, k$ to implicitly define a permutation of the agents. We use the convention that $i$ denotes the leftmost agent, $j$ denotes the middle agent, and $k$ denotes the rightmost agent.
%
We recall that given a nice mechanism $F$ with an approximation ratio of at most $\rho$ for $3$-agent instances, a $3$-agent instance $\vec{x}$ is \emph{$(i | j, k)$-well-separated} if $x_i < x_j < x_k$ and $\rho(x_k - x_j) < x_j - x_i$.

The following propositions show that if for some nice mechanism $F$, there is an $(i | j, k)$-well-separated instance $\vec{x}$ such that $F_2(\vec{x}) = x_j$, then as long as we ``push'' the locations of agents $j$ and $k$ to the right, while keeping the instance $(i | j, k)$-well-separated, the rightmost facility of $F$ stays with the location of agent $j$.
%
Intuitively, if for some $(i | j, k)$-well-separated instance $\vec{x}$, $F_2(\vec{x}) = x_j$, then agent $j$ serves as a dictator for all $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $x_j \leq x'_j$.


\begin{proposition}\label{prop:b_pushes_c}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_j$. Then for every instance $\vec{x}' = (\vec{x}_{-j}, x'_j)$ with $x_j < x'_j < x_k$, it holds that $F_2(\vec{x}') = x'_j$.
\end{proposition}

\begin{proof}
We first observe that any instance $\vec{x}' = (\vec{x}_{-j}, x'_j)$, with $x_j < x'_j < x_k$, is also $(i | j, k)$-well-separated.
%
To reach a contradiction, we assume that there is a point $y \in (x_j, x_k)$ such that $y \neq F_2(\vec{x}_{-j}, y)$. Hence $y \not\in I_j(x_i, x_k)$, and there is a $y$-hole $(l, r)$ in the image set $I_j(x_i, x_k)$. Let $y'$ be any point in the left half of $(l, r)$, e.g. let $y' = (2l+r)/3$. Then $l \in F(\vec{x}_{-j}, y')$. By Proposition~\ref{prop:middle}, $F_2(\vec{x}_{-j}, y') > y'$. This contradicts $F$'s bounded approximation ratio, since both $x_i$ and $y'$ are served by the facility at $l$, and $\cost[F(\vec{x}_{-j}, y')] \geq y' - x_i$, while the optimal cost is $x_k - y' > \rho(y' - x_i)$, because the instance $(\vec{x}_{-j}, y')$ is $(i | j, k)$-well-separated.
\qed \end{proof}


\begin{proposition}\label{prop:c_pulls_b}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_j$. Then for every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-k}, x'_k)$, $F_2(\vec{x}') = x_j$.
\end{proposition}


\begin{proof}
Since $F_2(\vec{x}) < x_k$, $x_k$ does not belong to the image set $I_k(x_i, x_j)$, and there is a $x_k$-hole $(l, r)$ in $I_k(x_i, x_j)$. Since $F_2(\vec{x}) = x_j$, the left endpoint of the $x_k$-hole is $l = x_j$ and the right endpoint is $r \geq 2x_k - x_j$.
%
Therefore, for all $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-k}, x'_k)$ with $x'_k < (r + l)/2$, $F_2(\vec{x}') = x_j$.

To conclude the proof, we show that there are no $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-k}, x'_k)$ with $x'_k \geq (r + l)/2$ and $F_2(\vec{x}') \neq x_j$.
%
To reach a contradiction, we assume that there exists a point $y \geq (r + l)/2$ such that $(\vec{x}_{-k}, y)$ is an $(i | j, k)$-well-separated instance and $F_2(\vec{x}_{-k}, y) \neq x_j$.
%
The existence of such a point $y$ implies the existence of a point $x'_k \in [(r + l)/2, r)$ ($x'_k$ may coincide with $y$) for which $\vec{x}' = (\vec{x}_{-k}, x'_k)$ is an $(i | j, k)$-well-separated instance. Then, $F_2(\vec{x}') = r > x'_k$, because the distance of $x'_k$ to $r \in I_k(x_i, x_j)$ is no greater than the distance of $x'_k$ to $l$.
%
Since $\vec{x}'$ is an $(i | j, k)$-well-separated instance, this contradicts Proposition~\ref{prop:interval}, according to which $F_2(\vec{x}) \in [x'_j, x'_k]$.
%
%Therefore, by Proposition~\ref{prop:middle}, $F_1(\vec{x}') \leq x_j$. Moreover, $x_j - F_1(\vec{x}') \leq x'_k - x_j$. Otherwise, agent $j$ has an incentive to report $x'_k$ and decrease his cost, since $x'_k \in F(x_i, x'_k, x'_k)$ due to the bounded approximation ratio of $F$.
%
%However, the fact that both $x_i$ and $x_j$ are served by $F_1(\vec{x}')$ contradicts $F$'s bounded approximation ratio, since $\cost[F(\vec{x}')] \geq x_j - x_i$, while the optimal cost is $x'_k - x_j < (x_j - x_i)/\rho$, because the instance $(\vec{x}_{-k}, x'_k)$ is $(i | j, k)$-well-separated.
\qed \end{proof}

\begin{proposition}\label{prop:right_cover_step}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_j$. For every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j, k\}}, x'_j, x'_k)$ with $x_j < x'_j \leq (x_j + x_k)/2$, it holds that $F_2(\vec{x}') = x'_j$.
\end{proposition}

\begin{proof}
Since $x'_j \leq (x_j + x_k) / 2 < x_k$, by Proposition~\ref{prop:b_pushes_c}, $F_2(\vec{x}_{-j}, x'_j) = x'_j$. Since the distance of $x'_j$ to $x_k$ is smaller than the distance of $x_j$ to $x_k$, the new instance $(\vec{x}_{-j}, x'_j)$ is $(i | j, k)$-well-separated. Therefore, by Proposition~\ref{prop:c_pulls_b}, for any $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j, k\}}, x'_j, x'_k)$, $F_2(\vec{x}') = x'_j$.
\qed \end{proof}


\begin{proposition}\label{prop:right_cover_3agents}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_j$. Then for every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j, k\}}, x'_j, x'_k)$ with $x_j \leq x'_j$, it holds that $F_2(\vec{x}') = x'_j$.
\end{proposition}

\begin{proof}
The proof follows by an inductive application of Proposition~\ref{prop:right_cover_step}. More specifically, by repeated applications of Proposition~\ref{prop:right_cover_step}, we keep moving the locations of agents $j$ and $k$ to the right, while keeping the resulting instance $(i | j, k)$-well-separated, and thus maintaining the location of the rightmost facility at the location of agent $j$.

Formally, let $d = x'_j - x_j$, let $\delta = (x_k - x_j)/2$, and let $\kappa = \ceil{d/\delta}$.
%
For every $\lambda = 1, \ldots, \kappa$, we inductively consider the instance $\vec{x}_\lambda = (\vec{x}_{-\{j, k\}}, x_j + (\lambda-1) \delta, x_k + (\lambda-1)\delta)$.
%
We observe that the instance $\vec{x}_\lambda$ is $(i | j, k)$-well-separated, because the distance of the locations of agents $j$ and $k$ is $2\delta$, while the distance of the locations of agents $i$ and $j$ is at least their distance in $\vec{x}$.
%
By inductively applying Proposition~\ref{prop:right_cover_step} to $\vec{x}_\lambda$, we obtain that for every $(i | j, k)$-well-separated instance $(\vec{x}_{-\{j,k\}}, y_j, y_k)$ with $x_j + (\lambda-1) \delta \leq y_j \leq x_j + \lambda \delta$, $F_2(\vec{x}_{-\{j,k\}}, y_j, y_k) = y_j$. For $\lambda = \kappa$, we conclude that $F_2(\vec{x}_{-\{j, k\}}, x'_j, x'_k) = x'_j$.
\qed\end{proof}



\subsection{Pushing the Pair of the Rightmost Agents to the Left: The Proof of Proposition~\ref{prop:left_cover}}
\label{app:s:push_left}

As in Section~\ref{app:s:push_right}, we explicitly prove Proposition~\ref{prop:left_cover} only for the $2$-Facility Location game and well-separated instances with $3$ agents (see also Proposition~\ref{prop:left_cover_3agents}). As before, it is not difficult to verify that the following propositions generalize to the $K$-Facility Location game and well-separated instances with $K+1$ agents.
%
%Moreover, one can establish the equivalent of the following propositions for well-separated instances where the two nearby agents are located elsewhere in the instance.


Next, we use the same notation as in Section~\ref{app:s:push_right}.
%
The following propositions show that if for some nice mechanism $F$, there is an $(i | j, k)$-well-separated instance $\vec{x}$ such that $F_2(\vec{x}) = x_k$, then as long as we ``push'' the locations of agents $j$ and $k$ to the left, while keeping the instance $(i | j, k)$-well-separated, the rightmost facility of $F$ stays with the location of agent $k$.
%
Intuitively, if for some $(i | j, k)$-well-separated instance $\vec{x}$, $F_2(\vec{x}) = x_k$, then agent $k$ serves as a dictator for all $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $x'_k \leq x_k$.


\begin{proposition}\label{prop:c_pushes_b}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_k$. Then for every instance $\vec{x}' = (\vec{x}_{-k},x'_k)$ with $x_j < x'_k < x_k$, it holds that $F_2(\vec{x}') = x'_k$.
\end{proposition}

\begin{proof}
To reach a contradiction, we assume that there is a point $x'_k \in (x_j, x_k)$ such that $x'_k \neq F_2(\vec{x}_{-k}, x'_k)$. Therefore, $x'_k \not\in I_k(x_i, x_j)$, and there is a $x'_k$-hole $(l, r)$ in the image set $I_k(x_i, x_j)$. We observe that $x_j \leq l$, since $x_j \in F(\vec{x}_{-k}, x_j)$, due to the bounded approximation ratio of $F$, and that $r \leq x_k$, since $F_2(\vec{x}) = x_k$.
%
Let $y_k$ be any point in the right half of $(l, r)$ different from $r$, e.g. let $y_k = (l+2r)/3$. We consider the instance $\vec{y} = (\vec{x}_{-k}, y_k)$, for which $F_2(\vec{y}) = r$, due to the strategyproofness of $F$.
%
Since $x_j < y_k < x_k$, $\vec{y}$ is an $(i | j, k)$-well-separated instance. Therefore, $F_2(\vec{y}) = r > y_k$ contradicts Proposition~\ref{prop:interval}, according to which $F_2(\vec{y}) \in [y_j, y_k]$.
%
%By Proposition~\ref{prop:middle}, $F_1(\vec{x}_{-k}, y') \leq x_j$. Moreover, $x_j - F_1(\vec{x}_{-k}, y') \leq y' - x_j$. Otherwise, agent $j$ has an incentive to report $y'$ and decrease his cost, since $y' \in F(\vec{x}_{-\{j,k\}}, y', y')$ due to the bounded approximation ratio of $F$.
%
%However, the fact that both $x_i$ and $x_j$ are served by $F_1(\vec{x}_{-k}, y')$ contradicts $F$'s bounded approximation ratio, since $\cost[F(\vec{x}_{-k}, y')] \geq x_j - x_i$, while the optimal cost is $y' - x_j > \rho(x_j - x_i)$, because $x_j < y' < x_k$, and thus the instance $(\vec{x}_{-k}, y')$ is $(i | j, k)$-well-separated.
\qed \end{proof}


\begin{proposition}\label{prop:b_pulls_c}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_k$. Then for every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-j}, x'_j)$, $F_2(\vec{x}') = x_k$.
\end{proposition}

\begin{proof}
Since $\vec{x}$ is $(i | j, k)$-well-separated, $F_1(\vec{x}) < x_j$ due to $F$'s bounded approximation ratio. Therefore, $x_j$ does not belong to the image set $I_j(x_i, x_k)$, and there is a $x_j$-hole $(l, r)$ in $I_j(x_i, x_k)$. Since $F_2(\vec{x}) = x_k$, the right endpoint of the $x_k$-hole is $r = x_k$ and the left endpoint is $l \leq 2x_j - x_k$.
%
Therefore, for all $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-j}, x'_j)$ with $x'_j > (r + l)/2$, $F_2(\vec{x}') = x_k$.

Next, we show that there are no $(i | j, k)$-well-separated instances $\vec{x}' = (\vec{x}_{-j}, x'_j)$ with $x'_j \leq (r + l)/2$ and $F_2(\vec{x}') \neq x_k$. To reach a contradiction, we assume that there exists a point $y \leq (r + l)/2$ such that $(\vec{x}_{-j}, x'_j)$ is $(i | j, k)$-well-separated and $F_2(\vec{x}_{-j}, y) \neq x_k$.
%
The existence of such a point $y$ implies the existence of a point $x'_j \in (l, (r + l)/2]$ ($x'_j$ may coincide with $y$) for which $\vec{x}' = (\vec{x}_{-j}, y)$ is an $(i | j, k)$-well-separated instance. Therefore, $l \in F(\vec{x}')$, because the distance of $x'_j$ to $l \in I_j(x_i, x_k)$ is no greater than the distance of $x'_j$ to $r$.
%
By Proposition~\ref{prop:middle}, $F_2(\vec{x}') \geq x'_j$, which implies that $F_2(\vec{x}') \geq x_k$. Since $x'_j$ lies in the left half of $(l, r)$, both $x_i$ and $x'_j$ are served by the facility at $l$, which contradicts $F$'s bounded approximation ratio, because $\cost[F(\vec{x}')] \geq x'_j - x_i$, while the optimal cost is $x_k - x'_j < (x'_j - x_i)/\rho$, because the instance $\vec{x}'$ is $(i | j, k)$-well-separated.
\qed \end{proof}

\begin{proposition}\label{prop:left_cover_step}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_k$. Then for every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $(x_k + x_j) / 2 \leq x'_k < x_k$, it holds that $F_2(\vec{x}') = x'_k$.
\end{proposition}

\begin{proof}
Since $x_j < x'_k < x_k$, by Proposition~\ref{prop:c_pushes_b}, $F_2(\vec{x}_{-k}, x'_k) = x'_k$. Since the distance of $x'_k$ to $x_j$ is smaller than the distance of $x_k$ to $x_j$, the new instance $(\vec{x}_{-k}, x'_k)$ is $(i | j, k)$-well-separated. Therefore, by Proposition~\ref{prop:b_pulls_c}, for any $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$, $F_2(\vec{x}') = x'_k$.
\qed \end{proof}


\begin{proposition}\label{prop:left_cover_3agents}
Let $\vec{x}$ be any $(i | j, k)$-well-separated instance with $F_2(\vec{x}) = x_k$. Then for every $(i | j, k)$-well-separated instance $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $x'_k \leq x_k$, it holds that $F_2(\vec{x}') = x'_k$.
\end{proposition}

\begin{proof}
The proof follows by an inductive application of Proposition~\ref{prop:left_cover_step}.
%
Let $d = x'_k - x_k$, let $\delta = (x'_k - x'_j)/2$, and let $\kappa = \ceil{d/\delta}$. We first observe that $F_2(\vec{x}_{-j}, x_k - 2\delta) = x_k$, by Proposition~\ref{prop:b_pulls_c}, since the instance $(\vec{x}_{-j}, x_k - 2\delta)$ is $(i | j, k)$-well-separated.
%
Next, for every $\lambda = 1, \ldots, \kappa$, we inductively consider the instance $\vec{x}_\lambda = (\vec{x}_{-\{j, k\}}, x_k - (\lambda+1) \delta, x_k - (\lambda-1)\delta)$.
%
We observe that the instance $\vec{x}_\lambda$ is $(i | j, k)$-well-separated, because the distance of the locations of agents $j$ and $k$ is $2\delta$, while the distance of the locations of agents $i$ and $j$ is at least their distance in $\vec{x}'$.
%
By inductively applying Proposition~\ref{prop:left_cover_step} to $\vec{x}_\lambda$, we obtain that for every $(i | j, k)$-well-separated instance $(\vec{x}_{-\{j,k\}}, y_j, y_k)$ with $x_k - \lambda \delta \leq y_k \leq x_k - (\lambda-1) \delta$, $F_2(\vec{x}_{-\{j,k\}}, y_j, y_k) = y_k$.
%
For $\lambda = \kappa$, we obtain that $F_2(\vec{x}_{-\{j, k\}}, x'_j, x'_k) = x'_k$.
\qed\end{proof}
